package com.code.test.second.backtracking;

/**
 *
 * N皇后问题
 */
public class SCode45 {
    /**
     * TODO 没学会
     */
    //q里面存的是每一行，皇后放置的下标
    static int[] q;

    public static void queen(int n) {
        int i = 1;//i标识当前行，也表示放置第i个皇后
        q = new int[n];
        q[i] = 0;//q[i]是当前列，每个新考虑的皇后初始位置 置为0列
        while (i >= 1) {
            q[i]++;//原位置移动一列
            //试探一个位置，是否能放进去
            //位置:(i,q[i])
            while (q[i] <= n && !canPlace(i)) {
                q[i]++;
            }

            //为第i个皇后找到了一个合适的位置:(i,q[i])
            if (q[i] <= n) {
                if (i == n) {
                    //如果已经到最后一行且已经都找到了，则打印解
                } else {
                    //还没有放置完，转向下一行，即开始下一个新皇后的放置
                    i++;
                    //每个新皇后的开始都是第一列
                    q[i] = 0;
                }
            } else {
                //若第i个皇后找不到合适的位置，则回溯到上一个皇后
                i--;
            }
        }
    }

    /**
     * 测试(i,q[i]) 位置上能否放置皇后
     *
     * @param i
     * @return
     */
    public static boolean canPlace(int i) {
        int j = 1;
        if (i == 1) {
            //第一行第一个位置可以直接放
            return true;
        }
        while (j < i) {
            //j=1 到i-1是已放置了皇后的行
            if (q[j] == q[i] || Math.abs(q[j] - q[i]) == Math.abs(j - i)) {
                //该皇后是否与之前的皇后同列
                //或者 (j,q[j]) 与 (i,q[i])是否同对角线
                return false;
            }
            j++;
        }
        return true;

    }


}
